vector<int> sortArrayByParityII(vector<int> &A) {
	vector B = A;
	int i = 0, j = 0;
	for (int k = 0; k < A.size(); k++) {
		if (k % 2 == 0) {
			for (; B[i] % 2 != 0; i++);
			A[k] = B[i++];
		} else {
			for (; B[j] % 2 != 1; j++);
			A[k] = B[j++];
		}
	}
	return A;
}

vector<int> sortArrayByParityII(vector<int> &A) {
	int n = A.size();
	int j = 1;
	for (int i = 0; i < n; i += 2) {
		if (A[i] % 2 == 1) {
			while (A[j] % 2 == 1) {
				j += 2;
			}
			swap(A[i], A[j]);
		}
	}
	return A;
}